package leetcode.year2021.month10;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _04_01TwoSum1 {
  public static void main(String[] args) {
    int[] nums = {3, 2, 4};
    int target = 6;
    int[] x = twoSum(nums, target);
    System.out.println(x[0]);
    System.out.println(x[1]);
  }
  public static int[] twoSum(int[] nums, int target) {
    //解法2，利用hashmap求值
    Map<Integer, Integer> numsMap = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
      int num2 = target - nums[i];
      if (numsMap.containsKey(num2) && numsMap.get(num2) != i){
        return new int[]{numsMap.get(num2),i};
      }
      numsMap.put(nums[i],i);
    }

    return new int[]{0,0};

    // 解法1 ，先排序，双指针找值
//    int[] sortedNums = nums.clone();
//    Arrays.sort(sortedNums);
//    int right = nums.length-1;
//    int left = 0;
//    while (left < right){
//      if (sortedNums[left] + sortedNums[right] == target){
//        break;
//      } else if (sortedNums[left] + sortedNums[right] < target){
//        left++;
//      } else if (sortedNums[left] + sortedNums[right] > target){
//        right--;
//      }
//    }
//
//    int leftNum = sortedNums[left];
//    int rightNum = sortedNums[right];
//
//    int[] result = new int[2];
//    int flag = 0;
//
//    for (int i = 0; i < nums.length; i++) {
//      if (nums[i] == leftNum || nums[i] == rightNum){
//        result[flag] = i;
//        flag++;
//      }
//      if (flag > 1){
//        break;
//      }
//    }
//    return result;
  }

  /**
   * 1. 两数之和
   * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
   *
   * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
   *
   * 你可以按任意顺序返回答案。
   *
   *
   *
   * 示例 1：
   *
   * 输入：nums = [2,7,11,15], target = 9
   * 输出：[0,1]
   * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
   * 示例 2：
   *
   * 输入：nums = [3,2,4], target = 6
   * 输出：[1,2]
   * 示例 3：
   *
   * 输入：nums = [3,3], target = 6
   * 输出：[0,1]
   */
}
